package GA;

import java.util.*;

public class Population implements GA_Param,Cloneable{
	private int pop_size;
	private int chromo_length;
	private int iters;
	
	private List<Chromosome> chromosomeList;
	private int[] curObjValueArray;
	private int[] curFitnessArray;
	private List<Integer> bestObjValueList;
	private Chromosome bestChromesome;

	/**
	 * Constructor.
	 * @param size -The size of the population.
	 * @param chromLength -The length of chromosome's gene.
	 * @param iters -Total number of iterations of population.
	 */
	public Population(int size,int chromLength,int iters){
		this.pop_size=size;
		this.chromo_length=chromLength;
		this.iters=iters;
		
		chromosomeList=new ArrayList<Chromosome>(pop_size);
		curObjValueArray=new int[pop_size];
		curFitnessArray=new int[pop_size];
		bestObjValueList=new ArrayList<Integer>(iters);
		bestChromesome=new Chromosome(chromo_length);

		for(int i=0;i<pop_size;++i){
			chromosomeList.add(new Chromosome(chromo_length));
		}
	}

	/**
	 * Population Deep clone!!!
	 */
	public Population clone(){
		Population p = null;  
		try{  
			p = (Population)super.clone();  
			List<Chromosome> list=new ArrayList<Chromosome>(pop_size);
			for(Chromosome elem:p.chromosomeList){
				list.add((Chromosome) elem.clone());
			}
			p.chromosomeList=list;
			p.curFitnessArray=p.curFitnessArray.clone();
			p.curObjValueArray=p.curObjValueArray.clone();
		}catch(CloneNotSupportedException e) {  
			e.printStackTrace();  
		}  
		return p;
	}

	/**
	 * Randomly setting the chromosome of the population.
	 */
	public void randomPop(){
		for(Chromosome elem:chromosomeList){
			elem.randomSetGene();
		}
	}

	/**
	 * Set primary population.
	 */
	public void setPrimaryPop(){
		int[] primaryGeneArray=new int[chromo_length];
		for(int col=0;col<chromo_length;++col){
			primaryGeneArray[col]=1;
		}
		for(Chromosome elem:chromosomeList){
			elem.setPrimaryGene(primaryGeneArray);
		}
	}

	/**
	 * Set primary population.
	 * @param gene -Ready gene array.
	 */
	public void setPrimaryPop(int[] gene){
		for(Chromosome elem:chromosomeList){
			elem.setPrimaryGene(gene);
		}
	}

	/**
	 * Repair the unreasonable chromosome of the current population.
	 */
	public void repair(){
		for(Chromosome elem:chromosomeList){
			elem.repair();
		}
	}

	/**
	 * Cross genes for the whole chromosome of list.
	 * @param p -List of Chromosome.
	 * @param rate -The probability of cross.
	 * @throws Exception:
	 */
	public static void cross(List<Chromosome> p, double rate) throws Exception{
		Random random=new Random();
		for(int i=0;i<p.size()/2;i+=1){
			if(random.nextDouble()<rate){
				Population.cross(p.get(2*i), p.get(2*i+1));
			}
		}
	}

	/**
	 * Swap two parts of two array in index of postion.
	 * @param array1 -one array
	 * @param array2 -another array
	 * @param index1 -one position
	 * @param index2 -annther position
	 * @throws Exception:
	 */
	private static void swapArrays(int[] array1,int[]array2,int index1,int index2) throws Exception{
		if(array1.length!=array2.length){
			throw new Exception("Array length is inconsistent!");
		}
		int start=Math.min(index1, index2);
		int end=index1+index2-start;

		int[] tempArray1=array1.clone();
		if (end - start >= 0) System.arraycopy(array2, start, array1, start, end - start);
		if (end - start >= 0) System.arraycopy(tempArray1, start, array2, start, end - start);
	}

	/**
	 * Exchange genes for a and b two chromosomes.
	 * @param a -chromosome one
	 * @param b -chromosome two
	 * @throws Exception:
	 */
	public static void cross(Chromosome a, Chromosome b) throws Exception{
		int cPoint1=(int) (Math.random()*CHROM_LENGTH);
		int cPoint2=(int) (Math.random()*CHROM_LENGTH);
		swapArrays(a.getGene(),b.getGene(),cPoint1,cPoint2);
	}

	/**
	 * Mutate chromosomes of the list at the fixed rate.
	 * @param p -list of Chromosome.
	 * @param rate -The probability of mutation.
	 */
	public static void mutate(List<Chromosome> p, double rate){
		for(Chromosome elem:p){
			elem.mutate(rate);
		}
	}

	/**
	 * Mutate chromosomes of the list at the mutable rate.
	 * @param p -The list of chromosome.
	 * @param rate -The array of mutation rate.
	 */
	public static void mutate(List<Chromosome> p, float[] rate){
		for(Chromosome elem:p){
			elem.mutate(rate);
		}
	}
	
	/**
	 * Carrying out cross and mutation on the current population.
	 * @param crossRate -The rate of cross.
	 * @param mutateRate -The rate of mutate.
	 * @return The population after crossing and mutating.
	 * @throws Exception:
	 */
	public Population reproduce(double crossRate, double mutateRate) throws Exception{
		// deep clone the current population.
		Population p=this.clone();
		Random random=new Random();
		// cross.
		for(int i=0;i<this.chromosomeList.size()/2;i+=1){
			if(random.nextDouble()<crossRate){
				Population.cross(chromosomeList.get(2*i), chromosomeList.get(2*i+1));	
			}
		}
		// mutate.
		for(Chromosome elem:this.chromosomeList){
			elem.mutate(mutateRate);
		}
		return p;
	}

	/**
	 * The two populations that current and param population p go on competing.
	 * @param p -a prePopulation.
	 * @return The list of chromosome was selected.
	 */
	public List<Chromosome> popCompetition(Population p){
		// Repair param population p.
		p.repair();

		double totalFitness=0;
		// Respectively calculate fitness.
		p.calcFitness();
		this.calcFitness();
		// Superposition of total fitness.
		for(int elem:curFitnessArray){
			totalFitness+=elem;
		}
		for(int elem:p.curFitnessArray){
			totalFitness+=elem;
		}
		// Accumulate probability and build wheel.
		double[] rateAccArray=new double[pop_size*2];
		rateAccArray[0]=curFitnessArray[0]/totalFitness;
		for(int i=1;i<pop_size;++i){
			rateAccArray[i]=rateAccArray[i-1]+curFitnessArray[i]/totalFitness;
		}
		for(int i=pop_size;i<pop_size*2;++i){
			rateAccArray[i]=rateAccArray[i-1]+p.curFitnessArray[i-pop_size]/totalFitness;
		}
		// Randomly generate 2*pop_size probabilities and sort.
		double[] randomRate=new double[pop_size];
		for(int i=0;i<pop_size;++i){
			randomRate[i]=Math.random();
		}
		Arrays.sort(randomRate);
		// Start Select.
		List<Chromosome> newPopList=new ArrayList<>();
		int newPopIndex=0,rateAccumulateIndex=0;
		while(newPopIndex<pop_size){
			if(randomRate[newPopIndex]<rateAccArray[rateAccumulateIndex]){
				Chromosome c=(Chromosome) p.chromosomeList.get(rateAccumulateIndex%pop_size).clone();
				newPopList.add(c);
				newPopIndex++;
			}
			else{
				rateAccumulateIndex++;
			}
		}
		return newPopList;
	}

	/**
	 * Acquire the objective function value of the chromosome in all population.
	 */
	public void calcObjValue(){
		for(int i=0;i<chromosomeList.size();++i){
			Chromosome elem=chromosomeList.get(i);
			curObjValueArray[i]=elem.calcObjValue();
		}
	}

	/**
	 * Sort the whole population according to the each chromosome's fitness.
	 */
	private void sortPopulation(){
		chromosomeList.sort(new Comparator<Chromosome>() {
			@Override
			public int compare(Chromosome o1, Chromosome o2) {
				return o2.getFitness() - o1.getFitness();
			}
		});
	}

	/**
	 * Acquire the min_value of the param array.
	 * @param array -The array was to be searched.
	 * @return the min value.
	 */
	private static int getMin(int[] array){
		int min=array[0];
		for(int elem:array){
			if(elem<min){
				min=elem;
			}
		}
		return min;
	}

	/**
	 * Calculate the fitness of each chromosome in population.
	 */
	public void calcFitness(){
		// Calculate objective value and be saved in curObjValueArray.
		this.calcObjValue();
		// Get Min objective value.
		int minObjValue=getMin(curObjValueArray);
		// Calculate fitness -> fitness=objValue-minObjvalue+100.
		for(int i=0;i<pop_size;++i){
			Chromosome elem=chromosomeList.get(i);
			int fitness=elem.getObjValue()-minObjValue+100;
			elem.setFitness(fitness);
			curFitnessArray[i]=fitness;
		}
	}

	/**
	 * Get the best individual of each generation and add the best objvalue.
	 * @return The best individual of the current population.
	 */
	private Chromosome getBestEach(){
		// Firstly Sort population based on objective value.
		sortPopulation();
		// Get chromosome that has Max objValue.
		Chromosome curBestIndividual=chromosomeList.get(0);
		int curBestValue=curBestIndividual.getObjValue();
		if(bestChromesome.getObjValue()<curBestValue){
			bestChromesome=(Chromosome) curBestIndividual.clone();
		}
		// The best Individual at the last generation.
		int lastBestValue=0;
		if(bestObjValueList.size()>=1){
			lastBestValue= bestObjValueList.get(bestObjValueList.size() - 1);
		}
		// If the current best individual is better, save it.
		bestObjValueList.add(Math.max(curBestValue, lastBestValue));
		return curBestIndividual;
	}

	/**
	 * Selecting a number of individuals from the current population for reproduction.
	 * @return List<>: A list of chromosome that was for reproduction.
	 */
	public List<Chromosome> select(){
		double totalFitness=0;
		for(int elem:curFitnessArray){
			totalFitness+=elem;
		}
		// Accumulate probability and build wheel.
		double[] rateAccArray=new double[pop_size];
		rateAccArray[0]=curFitnessArray[0]/totalFitness;
		for(int i=1;i<pop_size;++i){
			rateAccArray[i]=rateAccArray[i-1]+curFitnessArray[i]/totalFitness;
		}
		// Randomly generate pop_size probabilities and sort.
		double[] randomRate=new double[pop_size];
		for(int i=0;i<pop_size;++i){
			randomRate[i]=Math.random();
		}
		Arrays.sort(randomRate);
		// Start Select.
		List<Chromosome> newPopList=new ArrayList<>();
		int newPopIndex=0,rateAccumulateIndex=0;
		while(newPopIndex<pop_size){
			if(randomRate[newPopIndex]<rateAccArray[rateAccumulateIndex]){
				Chromosome c=(Chromosome) chromosomeList.get(rateAccumulateIndex).clone();
				newPopList.add(c);
				newPopIndex++;
			}
			else{
				rateAccumulateIndex++;
			}
		}
		return newPopList;
	}

	/**
	 * Renew the population according to param List of chromosome.
	 * @param p -The list of chromosome.
	 */
	public void reNewPop(List<Chromosome> p){
		int index=0;
		Chromosome bestIndividual=this.getBestEach();
		chromosomeList.clear();
		if(bestIndividual.calcObjValue()>p.get(0).calcObjValue()){
			chromosomeList.add((Chromosome) bestIndividual.clone());
			index++;		
		}

		for(int i=index;i<p.size();++i){
			chromosomeList.add(p.get(i));
		}
	}

	/**
	 * Print the each chromosome's objvalue at the every generation.
	 */
	public void printAllObjValue(){
		this.calcObjValue();
		for(Chromosome elem:chromosomeList){
			System.out.print(elem.getObjValue()+" ");
		}
		System.out.print("\n");
	}

	/**
	 * Print current best individual and its gene.
	 * @param isLast -Only print the last generation's record in MAX_ITER generations.
	 */
	public void printBestInfo(boolean isLast){
		if(isLast){
			System.out.print(bestObjValueList.get(iters - 1) +"  ");
		}
		else{
			for(Integer e:bestObjValueList){
				System.out.print(e +" ");
			}
		}
		System.out.print(" ");
		bestChromesome.printGene();
		System.out.print("\n");
	}

	/**
	 * Acquire the best individual chromosome.
	 * @return The best Chromosome.
	 */
	public Chromosome getBest(){
		return bestChromesome;
	}
}
